package com.zhang;


/**
 * 优化过的动态数组 （减少插入和删除过程中数组的复杂度）
 *
 * @param <E> 泛型
 */
public class ArrayList2<E> implements List<E> {
    private int size;

    private E[] elements;

    /**
     * 添加一个指针 --> 指向数组开始的位置
     */
    private int start;

    /**
     * 设置默认的初始化空空间
     */
    private static final int CAPACITY_DEFAULT = 5;

    /**
     * 元素不存在
     */
    private static final int ELEMENT_NOF_FOUND = -1;

    public ArrayList2(int capacity) {
        capacity = capacity < CAPACITY_DEFAULT ? CAPACITY_DEFAULT : capacity;
        elements = (E[]) new Object[capacity];
    }

    public ArrayList2() {
        this(CAPACITY_DEFAULT);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != ELEMENT_NOF_FOUND;
    }

    @Override
    public void add(E element) {
        add(size, element);
    }

    @Override
    public E get(int index) {
        // O(1)
        rangeCheck(index);
        return elements[covertIndex(index)];
    }

    @Override
    public E set(int index, E element) {
        // O(1)
        rangeCheck(index);
        int newIndex = covertIndex(index);
        E oldElement = elements[newIndex];
        elements[newIndex] = element;
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        /**
         * 最好: O(1)
         * 最坏: O(n)
         * 平均: O(n) (1+2+3+....+n)/n
         */
        // 范围检查
        rangeCheckForAdd(index);
        // 确保扩容
        ensureCapacity();
        // 移动数据,从后开始迁移
        if (index >= size / 2) {
            // 移动index到size的元素
            for (int i = (size + start); i > (index + start); i--) {
                elements[(i + elements.length) % elements.length] = elements[(i - 1 + elements.length) % (elements.length)];
            }
        } else {
            // 移动0到index的元素
            for (int i = start; i < index + start; i++) {
                elements[(i - 1 + elements.length) % elements.length] = elements[i % elements.length];
            }
            start = (start - 1 + elements.length) % elements.length;
        }
        // 设置元素
        elements[covertIndex(index)] = element;
        size++;
    }

    /**
     * 确保数组的扩容
     */
    private void ensureCapacity() {
        // 获取数组的长度
        int oldLength = elements.length;
        // 如果当前容量小于数组的长度
        if (size + 1 < oldLength) {
            return;
        }
        // 需要扩容,设置新的长度
        int newCapacity = oldLength + (oldLength >> 1);
        // 创建新数组
        E[] newElements = (E[]) new Object[newCapacity];
        // 数据迁移到新数组
        for (int i = 0, j = start; i < size; i++, j++) {
            newElements[i] = elements[j % oldLength];
        }
        start = 0;
        elements = newElements;
    }

    @Override
    public E remove(int index) {
        /**
         * 最好: O(1)
         * 最坏: O(n)
         * 平均: O(n) (1+2+3+....+n)/n
         *
         * TODO remove 这边还有点问题
         */
        // 范围检查
        rangeCheck(index);
        // 获取要删除的元素
        E oldElement = elements[covertIndex(index)];
        if (index <= size / 2) {
            for (int i = index; index <= 0; i--) {
                elements[covertIndex(i)] = elements[covertIndex(i - 1)];
            }
            start = (start + 1) % elements.length;
        } else {
            for (int i = index; index < size; i++) {
                elements[covertIndex(i)] = elements[covertIndex(i + 1)];
            }
        }
        // 设置元素
        elements[covertIndex(index)] = null;
        size--;
        return oldElement;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[covertIndex(i)] == null) {
                    return i;
                }
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[covertIndex(i)])) {
                    return i;
                }
            }
        }

        return ELEMENT_NOF_FOUND;
    }

    @Override
    public void clear() {
        // 将所有位置置为空
        for (int i = 0; i < size; i++) {
            elements[covertIndex(i)] = null;
        }
        size = 0;
        start = 0;
    }

    /**
     * 添加元素的index 范围校验
     *
     * @param index index位置
     */
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException(outOfIndexMsg(index));
        }
    }

    /**
     * index 范围校验
     *
     * @param index index位置
     */
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException(outOfIndexMsg(index));
        }
    }

    /**
     * 通过index构造index不合法的提示信息
     */
    private String outOfIndexMsg(int index) {
        return "Index: " + index + ", size:" + size;
    }


    /**
     * 将index转化成真实的index
     */
    public int covertIndex(int index) {
        return (index + start + elements.length) % elements.length;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size = ").append(size).append(", [");
        for (int i = 0; i < elements.length; i++) {
            if (i != 0) {
                string.append(",");
            }
            if (elements[i] == null) {
                string.append("null");
            } else {
                string.append(elements[i]);
            }
        }
        string.append("]");
        return string.toString();
    }
}
